package com.xxd.algo.newcode.mid02.class04;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-10-16 12:56
 */
public class Code02_MoneyWays {

    /**
     * 普通币动态规划
     *
     * @param arr
     * @param money
     * @return
     */
    public static int[][] getDpArb(int[] arr, int money) {
        if (arr == null || money == 0) {
            return null;
        }

        // dp[i][j] 普通币自由选择i张，刚好凑成j元的 方法数
        // i 0....arr.length - 1
        // j 0...money
        int[][] dp = new int[arr.length][money + 1];

        for (int i = 0; i < arr.length; i++) {// 凑0元 的方法数
            dp[i][0] = 1;
        }

        for (int j = 1; arr[0] * j <= money; j++) { // 第一种币值，能凑的方法数
            dp[0][arr[0] * j] = 1;
        }

        // 普通位置
        // 1、不要当前币
        // 2、要当前币
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
            }
        }

        return dp;
    }


    public static int[][] getDpOne(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] dp = new int[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
            }
        }
        return dp;
    }
}
